#include<stdio.h>
#include<math.h>
/*
	RSA算法是一种非对称密码算法。
	所谓非对称，就是指该算法需要一组密钥，其中包括公钥和私钥。
	RSA加密或解密步骤如下:
	1．获取公钥与私钥
	(1)随意选择两个大的质数p和q，p不等于q，计算n=pq。
	(2)计算不大于n且与n互质的整数个数f，公式为f=(p-1)(q-1)。
	(3)选择一个整数e与(p-1)(q-1)互质，并且e小于(p-1)(q-1).
	(4)计算d，公式为de mod (p-1)(q-1)=1。
	(5)d和n是私钥，p、q、e是公钥。

	2.加密过程
	设e为加密密钥，明文为m，密文为c，则加密公式如下:
	c=(m^e) mod n
	3．解密过程
	设e为加密密钥，明文为m，密文为c，d为解密密钥，则解密公式如下:
	m=(c^d) mod n
	
*/
//判断是否是素数
int judgePrime(int num)
{
	int i,flag=1;
	for(i=2;i<num;i++)
	{
		if(num%i==0)
		{
			flag=0;
			return flag;
		}
	}
	return flag;
}
int RSA(int a,int b,int c)
{
	/*
	2.加密过程
		设e为加密密钥，明文为m，密文为c，则加密公式如下:
		c=(m^e) mod n
	3．解密过程
		设e为加密密钥，明文为m，密文为c，d为解密密钥，则解密公式如下:
		m=(c^d) mod n
	*/
	int result=1;
	b=b+1;
	while(b!=1)
	{
		result=result*a;
		result=result%c;
		b--;
	}
	printf("%d\n",result);
	//int r=(int)pow((double)a,(double)b);
	//printf("r:%d\n",r%c);
	return result;
	
}
int main()
{
	int p,q,n,f,e,d,m,choose,c;
	printf("please input the p,q:\n");
	scanf("%d%d",&p,&q);
	if(judgePrime(p)&&judgePrime(q)&&p!=q)			//判断p，q是否同时是质数,且p!=q
	{
		n=p*q;										//计算n=pq
		printf("the n is %d\n",n);
		f=(p-1)*(q-1);								//计算不大于n且与n互质的整数个数f，公式为f=(p-1)(q-1)。
		printf("the f is %d\n",f);
		printf("please input the e:\n");
		scanf("%d",&e);								//选择一个整数e与(p-1)(q-1)互质，并且e小于(p-1)(q-1).
		if(e<1||e>f)
		{
			printf("e input error, please input again!\n");
			scanf("%d",&e);
		}
		d=1;										//d赋值为1
		while((d*e)%f != 1)							//计算d，公式为de mod (p-1)(q-1)=1
		{
			d++;
		}
		printf("then caculate out the d is %d\n",d);
		printf("加密请选择1:\n");
		printf("解密请选择2:\n");
		scanf("%d",&choose);
		switch(choose)
		{
			case 1:
				printf("请输入要加密的数字m:\n");
				scanf("%d",&m);
				c=RSA(m,e,n);						//加密获取密文
				printf("密文为:%d\n",c);
				break;
			case 2:
				printf("请输入要解密的数字c:\n");
				scanf("%d",&c);
				m=RSA(c,d,n);						//解密获取明文
				printf("明文为:%d\n",m);
				break;
			default:
				printf("input choose number error!\n");
				break;
		}
	}
	else
	{
		printf("输入p或q值有误!\n");
		return 0;
	}
	return 0;
}
